/*
 * @lc app=leetcode.cn id=1801 lang=javascript
 *
 * [1801] 积压订单中的订单总数
 */

// @lc code=start

// 堆
class PQ {
  constructor(keys = [], mapKeysValue = (x) => x) {
    this.keys = [...keys];
    this.mapKeysValue = mapKeysValue;

    for (let i = (this.keys.length - 2) >> 1; i >= 0; i--) {
      this.sink(i);
    }
  }

  less(i, j) {
    return this.mapKeysValue(this.keys[i]) < this.mapKeysValue(this.keys[j]);
  }

  exch(i, j) {
    [this.keys[i], this.keys[j]] = [this.keys[j], this.keys[i]];
  }

  swin(index) {
    let parent = (index - 1) >> 1;
    while (parent >= 0 && this.less(parent, index)) {
      this.exch(parent, index);
      index = parent;
      parent = (parent - 1) >> 1;
    }
  }

  sink(index) {
    let child = index * 2 + 1;
    let len = this.keys.length;
    while (child < len) {
      if (child + 1 < len && this.less(child, child + 1)) {
        child++;
      }
      if (this.less(child, index)) break;

      this.exch(child, index);
      index = child;
      child = index * 2 + 1;
    }
  }

  size() {
    return this.keys.length;
  }

  insert(key) {
    this.keys.push(key);
    this.swin(this.keys.length - 1);
  }

  poll() {
    let head = this.peek();
    this.exch(0, this.size() - 1);
    this.keys.pop();
    this.sink(0);
    return head;
  }

  peek() {
    return this.keys[0];
  }
}
// 大顶堆
class MaxPQ extends PQ {}
// 小顶堆
class MinPQ extends PQ {
  constructor(keys, mapKeysValue = (x) => x) {
    super(keys, (x) => -1 * mapKeysValue(x));
  }
}

/**
 * @param {number[][]} orders
 * @return {number}
 */
var getNumberOfBacklogOrders = function (orders) {
  const buy = new MaxPQ([], (x) => x[0]);
  const sell = new MinPQ([], (x) => x[0]);

  for (let order of orders) {
    if (order[2] === 0) {
      // 采购订单
      while (order[1] !== 0 && sell.size() && sell.peek()[0] <= order[0]) {
        let count = Math.min(sell.peek()[1], order[1]);
        order[1] -= count;
        sell.peek()[1] -= count;
        if (sell.peek()[1] === 0) sell.poll();
      }
      // 处理后的采购订单，如果还有订单数量，就放入堆中等待下次处理
      if (order[1] !== 0) buy.insert(order);
    } else if (order[2] === 1) {
      // 销售订单
      while (order[1] !== 0 && buy.size() && order[0] <= buy.peek()[0]) {
        let count = Math.min(buy.peek()[1], order[1]);
        order[1] -= count;
        buy.peek()[1] -= count;
        if (buy.peek()[1] === 0) buy.poll();
      }
      // 处理后的销售订单，如果还有订单数量，就放入堆中等待下次处理
      if (order[1] !== 0) sell.insert(order);
    }
  }

  let result = 0;
  const mod = 10 ** 9 + 7;

  for (let order of buy.keys) {
    result = (result + order[1]) % mod;
  }

  for (let order of sell.keys) {
    result = (result + order[1]) % mod;
  }

  return result;
};
// @lc code=end
